package test.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class Permutations<T> {
	
	public static void main(String args[]) {
		
		Permutations<Integer> obj = new Permutations<Integer>();
		Collection<Integer> input = new ArrayList<Integer>();
		for (int i=1; i<=4; i++) {
			input.add(i);
		}
		
		Collection<List<Integer>> output = obj.permute4Path(input);
		
		printPermutes(output);
    }
	
	public Collection<List<T>> permute4Path(Collection<T> input) {
		
		Collection<List<T>> output = new ArrayList<List<T>>();
		
		if (input.isEmpty()) {
			output.add(new ArrayList<T>());
			return output;
		}
		
		List<T> list = new ArrayList<T>(input);
		T head = list.get(0);
		List<T> rest = list.subList(1, list.size());
		for (List<T> permutations : permute4Path(rest)) {
			List<List<T>> subLists = new ArrayList<List<T>>();
			for (int i = 0; i <= permutations.size(); i++) {
			    List<T> subList = new ArrayList<T>();
			    subList.addAll(permutations);
			    subList.add(i, head);
			    subLists.add(subList);
			}
			output.addAll(subLists);
		}
		return output;
	}
	
	public Collection<List<T>> permute(Collection<T> input) {
		
		Collection<List<T>> output = new ArrayList<List<T>>();
		
		if (input.isEmpty()) {
			output.add(new ArrayList<T>());
			return output;
		}
		
		List<T> list = new ArrayList<T>(input);
		T head = list.get(0);
		List<T> rest = list.subList(1, list.size());
		for (List<T> permutations : permute(rest)) {
			List<List<T>> subLists = new ArrayList<List<T>>();
			for (int i = 0; i <= permutations.size(); i++) {
			    List<T> subList = new ArrayList<T>();
			    subList.addAll(permutations);
			    subList.add(i, head);
			    subLists.add(subList);
			}
			output.addAll(subLists);
		}
		return output;
	}
	
	public static void printPermutes(Collection<List<Integer>> output) {
		Iterator<List<Integer>> iter = output.iterator();
		while (iter.hasNext()) {
			List<Integer> list = iter.next();
			System.out.println(Arrays.toString(list.toArray()));
		}
	}
}
